Processing math: 100%
We use cookies to improve your experience with our site.

Indexed in:

SCIE, EI, Scopus, INSPEC, DBLP, CSCD, etc.

Submission System
(Author / Reviewer / Editor)
Advanced Search
Volume 23 Issue 4
July  2008
Turn off MathJax
Article Contents
Abstract
References
Related Articles
Ji-Gang Wu, Thambipillai Srikanthan, Guang-Wei Zou. New Model and Algorithm for Hardware/Software Partitioning[J]. Journal of Computer Science and Technology, 2008, 23(4): 644-651.
Citation: Ji-Gang Wu, Thambipillai Srikanthan, Guang-Wei Zou. New Model and Algorithm for Hardware/Software Partitioning[J]. Journal of Computer Science and Technology, 2008, 23(4): 644-651.
shu

New Model and Algorithm for Hardware/Software Partitioning

  • Centre for High Performance Embedded Systems, School of Computer Engineering, Nanyang Technological University, 639798, Singapore

More Information
  • Received Date: August 07, 2007
  • Revised Date: May 20, 2008
  • Published Date: July 09, 2008
    Abstract
  • This paper focuses on the algorithmic aspects for the hardware/software(HW/SW) partitioning which searches a reasonable composition of hardwareand software components which not only satisfies the constraint ofhardware area but also optimizes the execution time. The computationalmodel is extended so that all possible types of communications can betaken into account for the HW/SW partitioning. Also, a new dynamicprogramming algorithm is proposed on the basis of the computational model,in which source data, rather than speedup in previous work, of basicscheduling blocks are directly utilized to calculate the optimalsolution. The proposed algorithm runs in O(n⋅A) for n codefragments and the available hardware area A. Simulation results showthat the proposed algorithm solves the HW/SW partitioning withoutincrease in running time, compared with the algorithm cited in theliterature.
    • FullText(HTML)
    • References (20)
  • [1] Niemann R, Marwedel P. Hardware/software partitioning using integer programming. In {\it Proc. the IEEE/ACM European Design Automation Conference (EDAC)}, Paris, France, March 1996, pp.473--479.
    [2]
    } Gupta R, Micheli G D. Hardware-software cosynthesis for digital systems. {\it IEEE Design and Test of Computers}, 1993, 10(3): 29--41.
    [3]
    } Gupta R K, Coelho C, De Micheli G. Synthesis and simulation of digital systems containing interacting hardware and software components. In {\it Proc. the 29th ACM/IEEE Design Automation Conference}, Los Alamitos, CA, USA, June 1992, pp.225--230.
    [4] }Ernst R, Henkel J, Benner T. Hardware-software co-synthesis for micro-controllers. {\it IEEE Design and Test of Computer}, 1993, 10(4): 64--75.
    [5] }Vahid F, Gajski D D, Gong J. A binary-constraint search algorithm for minimizing hardware during hardware/software partitioning. In {\it Proc. IEEE/ACM European Design Automation Conference (EDAC)}, Paris, France, February 1994, pp.214--219.
    [6] }Vahid F, Gajski D D. Clustering for improved system-level functional partitioning. In {\it Proc. the 8th International Symposium on System Synthesis}, Cannes, France, September 1995, pp.28--33.
    [7] }Quan G, Hu X, Greenwood G W. Preference-driven hierarchical hardware/software partitioning. In {\it Proc. IEEE International Conference on Computer Design}, Austin, TX, USA, October 1999, pp.652--657.
    [8] }Srinivasan V, Radhakrishnan S, Vemuri R. Hardware software partitioning with integrated hardware design space exploration. In {\it Proc. DATE'98}, Paris, France, February 1998, pp.28--35.
    [9] }Niemann R, Marwedel P. An algorithm for hardware/software partitioning using mixed integer linear programming. {\it Design Automation for Embedded Systems}, Special Issue: Partitioning Methods for Embedded Systems, 1997, 2(2): 165--193.
    [10]
    } Weinhardt M. Integer programming for partitioning in software oriented codesign. {\it Lecture Notes in Computer Science}, 1995, 975: 227--234.
    [11] }Peng Z, Kuchcinski K. An algorithm for partitioning of application specific system. In {\it Proc. IEEE/ACM European Design Automation Conference (EDAC)}, Paris, February 1993, pp.316--321.
    [12]
    } Henkel J, Ernst R. An approach to automated hardware/software partitioning using a flexible granularity that is driven by high-level estimation techniques. {\it IEEE Trans. VLSI Sys.}, 2001, 9(2): 273--289.
    [13] }Eles P, Peng Z, Kuchcinski K, Dobolt A. System level hardware/software partitioning based on simulated annealing and tabu search. {\it Design Automation for Embedded Systems}, 1997, 2(1): 5--32.
    [14] }Karam S C, Ranga V. Hardware-software partitioning and pipelined scheduling of transformative applications. {\it IEEE Transactions on Very Large Scale Integration (VLSI) Systems}, 2002, 10(3): 193--208.
    [15]
    } Madsen J, Grode J, Knudsen P V, Petersen M E, Haxthausen A. LYCOS: The Lyngby co-synthesis system. {\it Design Automation for Embedded Systems}, 1997, 2: 195--235.
    [16] }Wu Jigang, Srikanthan T. Low-complex dynamic programming algorithm for hardware/software partitioning. {\it Information Processing Letters}, 2006, 98: 41--46.
    [17]
    } Edwards S A, Lavagno L, Lee E A {\it et al}. Design of embedded systems: Formal models validation, and synthesis. In {\it Proc. the IEEE}, 1997, 85(3): 366--390.
    [18]
    } Vallejo M L, Lopez J C. On the hardware-software partitioning problem: System modeling and partitioning techniques. {\it ACM Transactions on Design Automation of Electronic Systems}, 2003, 8(3): 269--297.
    [19] }Pisinger D. Algorithms for knapsack problems [Dissertation]. University of Copenhagen, 1995.
    [20] }Arato P, Mann Z A, Orban A. Algorithmic aspects of hardware/software partitioning. {\it ACM Transactions on Design Automation of Electronic Systems}, 2005, 10(1): 136--156.
    • Relative Articles

  • Related Articles

    [1]Qi Ge, Hai-Tao Wang, Hong Zhu. An Improved Algorithm for Finding the Closest Pair of Points[J]. Journal of Computer Science and Technology, 2006, 21(1): 27-31.
    [2]Dao-Yun Xu, Zhi-Hong Tao. Complexities of Homomorphism and Isomorphism for Definite Logic Programs[J]. Journal of Computer Science and Technology, 2005, 20(6): 758-762.
    [3]Xi-Shun Zhao. Regular Disjunction-Free Default Theories[J]. Journal of Computer Science and Technology, 2004, 19(3).
    [4]ZHU Daming, LUAN Junfeng, MA Shaohan. Hardness and Methods to Solve CLIQUE[J]. Journal of Computer Science and Technology, 2001, 16(4).
    [5]GAO Suixiang, LIN Guohui. Decision Tree Complexity of Graph Properties with Dimension at Most5[J]. Journal of Computer Science and Technology, 2000, 15(5): 416-422.
    [6]JIANG Tao, LI Ming, Paul M.B. Average-Case Analysis of Algorithms Using Kolmogorov Complexity[J]. Journal of Computer Science and Technology, 2000, 15(5): 402-408.
    [7]GAO Suixiang, LIN Guohui. Decision Tree Complexity of Graph Properties with Dimension at Most 5[J]. Journal of Computer Science and Technology, 2000, 15(5).
    [8]WU Jigang, JI Yongchang, CHEN Guoliang. An Optimal Online Algorithm for Half Plane Intersection[J]. Journal of Computer Science and Technology, 2000, 15(3): 295-299.
    [9]GAO Xiaoshan, ZHU Changcai. Automated Generation of Kempe Linkageand Its Complexity[J]. Journal of Computer Science and Technology, 1999, 14(5): 460-467.
    [10]Huang Wenqi, Li Wei. A Hopeful CNF-SAT─Algorithm Its High Efficiency, Industrial Application and Limitation[J]. Journal of Computer Science and Technology, 1998, 13(1): 9-12.
    • Supplements (0)

Catalog

    Get Citation
    XML
    Article views (31) PDF downloads (1597) Cited by()
    Related

    Copyright ©2025 JCST, All Rights Reserved     京ICP备05002829号-1

    Institute of Computing Technology, Chinese Academy of Sciences
    P.O. Box 2704, Beijing 100190, P.R. China

    Tel.: 86-10-62610746 E-mail: jcst@ict.ac.cn

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return